// 课程表 II

/*
 现在你总共有 n 门课需要选，记为 0 到 n-1。
 
 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
 
 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
 
 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
 */
import Foundation

func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
    var edges: [Int: [Int]] = [:]
    var counter: [Int: Int] = [:]
    
    for prerequisite in prerequisites {
        edges[prerequisite[1], default: []].append(prerequisite[0])
        counter[prerequisite[0], default: 0] += 1
    }
    
    var queue: [Int] = []
    
    for i in 0 ..< numCourses {
        if counter[i] == nil {
            queue.append(i)
        }
    }
    
    var result: [Int] = []
    
    while !queue.isEmpty {
        let num = queue.removeFirst()
        result.append(num)
        
        for e in edges[num] ?? [] {
            if let count = counter[e] {
                if count == 1 {
                    queue.append(e)
                } else {
                    counter[e] = count - 1
                }
            }
        }
    }
    
    if result.count != numCourses {
        return []
    } else {
        return result
    }
}
